//================v1要点总结===============
/**
 * 1.在v1的基础上进行优化
 */

/**
 * 
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
    let len = triangle.length;
    // 复制
    let minPath = new Array(len).fill(0);
    // 从第一层开始，每一层都要与对应的上一层路径最小值相加，得到新一层的最小值
    for (let i = 0; i < len; i++) {
        let j = i;
        // 第一个的最小路径就是上一行的第一个最小路径
        while (j > 0) {
            // 除了第一个和最后一个，当前的最短路径为当前值 + 上一层的最短路径i - 1 和 i
            minPath[j] = triangle[i][j] + Math.min(minPath[j], minPath[j - 1])
            j--;
        }
        // 第一个的最小路径就是上一行的第一个最小路径
        minPath[0] += triangle[i][0]
        // 将下一行最后一个数据的i位置最小路径补全为i-1位置的值。
        if (i + 1 < len) {
            minPath[i + 1] = minPath[i]
        }

    }
    return Math.min(...minPath)
};

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))